package leetcode.practice;

/**
 * 无需数组查找第K个大的数
 */
public class NoSortArrayFindK {

    public Integer quickSort(int[] arr, int k) {
        if (k <= 0 || k > arr.length) {
            return null;
        }
        sort(arr, 0, arr.length - 1);


        // 倒数第k个的坐标
        // 第一步：倒数第k个 等于正数 n - k + 1个
        // 第二步：正数第 n - k + 1个的坐标为 n - k
        // 即倒数第k 的坐标为 n - k

        return arr[arr.length - k];
    }

    public void sort(int[] arr, int left, int right) {
        if (left <= right) {
            return;
        }

        int i = left, j = right;
        int index = arr[i];
        while (i < j) {

            // 为什么数等于，因为要找到第一个比index小的数，等于的跳过
            while (i < j && arr[j] >= index) {
                j--;
            }

            // 此时 arr[j] 小于 index，需要把它移到前面去
            if (i < j) {
                // i 本身的值已经被赋值给index了
                // i 赋值之后，继续往后遍历
                // 此时 j 位置的值是重复的，下一次要把 后一个j的值改成其他的值
                arr[i] = arr[j];
                i++;
            }

            // 从前往后找到第一个比index大的数
            while (i < j && arr[i] <= index) {
                i++;
            }

            // 此时 arr[i] 大于 index，需要把它移到后面去
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
            // 最后一步
            // index = 5
            // ... -> 3 -> 7(i) -> 2(j) -> ...
            // ... -> 3 -> 7(i j) -> 7 -> ...

            // 至此，此时 i 可能后移了， j 可能前移了。但是i j 之间可能还有不满足条件的数字，下一次循环从j--位置开始遍历
        }
        // 3 -> 5(i j) -> 7
        arr[i] = index;
        // i 为中间值，左边的都小于等于 index ；右边的都大于等于 index。
        sort(arr, left, i - 1);
        sort(arr, i + 1, right);
    }
}
